//
// Created by sai on 2019/2/18.
//
#include <stdlib.h>
#include <stdio.h>
#include "MergeSort_C11.h"

void Merge(ElementType A[], ElementType TmpArray[], int Left, int Center, int Right) {
    int TmpPos, Lpos, Rpos, LeftEnd, NumElements;
    TmpPos = Left;
    Lpos = Left;
    Rpos = Center+1;
    LeftEnd = Center;
    NumElements = Right - Left + 1;
    while (Lpos <= LeftEnd && Rpos <= Right) {
        if (A[Lpos] <= A[Rpos])
            TmpArray[TmpPos++] = A[Lpos++];
        else
            TmpArray[TmpPos++] = A[Rpos++];
    }
    while (Lpos <= LeftEnd)
        TmpArray[TmpPos++] = A[Lpos++];
    while (Rpos <= Right)
        TmpArray[TmpPos++] = A[Rpos++];
    for (int i = Left; i <Right; i++)
        A[i] = TmpArray[i];

}

void Msort(ElementType A[], ElementType TmArray[], int Left, int Right) {
    int Center;
    if (Left < Right) {
        Center = (Left + Right) / 2;
        Msort(A, TmArray, Left, Center);
        Msort(A, TmArray, Center + 1, Right);
        Merge(A, TmArray, Left, Center, Right);
    }
}

void Mergesort(ElementType A[], int N) {
    ElementType *TmpArray;
    TmpArray = malloc(N * sizeof(ElementType));
    if (TmpArray != NULL) {
        Msort(A, TmpArray, 0, N - 1);
        free(TmpArray);
    } else
        puts("No space for tmp array!!!");

}




